package cn.fansunion.leecode.collection;

import java.util.Stack;

/**
 * 20. 有效的括号 <br/>给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 
 * 有效字符串需满足：
 * 
 * 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。  
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-18
 */
public class ValidParentheses {
    /* 示例 1：
    
    输入：s = "()"
    输出：true
    示例 2：
    
    输入：s = "()[]{}"
    输出：true
    示例 3：
    
    输入：s = "(]"
    输出：false
    示例 4：
    
    输入：s = "([)]"
    输出：false
    示例 5：
    
    输入：s = "{[]}"
    输出：true*/
    /**
     * 遍历字符串中的字符，遇到左括号，放到stack；遇到右括号，和栈顶的元素进行配对；如果匹配，移除栈顶，再遍历下一个；否则，返回false
     * todo：优化点，维护一个map：右括号为key，左括号为value
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        if (s == null || s.length() % 2 == 1) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int index = 0; index < s.length(); index++) {
            char ch = s.charAt(index);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.add(ch);
            } else if (ch == ')') {
                if(stack.isEmpty()) {
                    return false;
                }
                Character top = stack.peek();
                //遍历中匹配了
                if (top != null && top.equals('(')) {
                    stack.pop();
                } else {
                    return false;
                }
            } else if (ch == ']') {
                if(stack.isEmpty()) {
                    return false;
                }
                Character top = stack.peek();
                //遍历中匹配了
                if (top != null && top.equals('[')) {
                    stack.pop();
                } else {
                    return false;
                }
            } else if (ch == '}') {
                if(stack.isEmpty()) {
                    return false;
                }
                Character top = stack.peek();
                //遍历中匹配了
                if (top != null && top.equals('{')) {
                    stack.pop();
                } else {
                    return false;
                }
            } else {
                throw new IllegalArgumentException("param valid");
            }
        }
        //全部成对匹配的情况，是：入栈和出栈了，剩余元素为0
        return stack.size()==0;

    }
    
    /**
     * 遍历字符串中的字符，遇到左括号，放到stack；遇到右括号，和栈顶的元素进行配对；如果匹配，移除栈顶，再遍历下一个；否则，返回false
     * 问题点：用例不够全，自测不到位，"){"，右括号开头的或者奇数位是右括号的
     * @param s
     * @return
     */
    public boolean isValidError(String s) {
        if (s == null || s.length() % 2 == 1) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int index = 0; index < s.length(); index++) {
            char ch = s.charAt(index);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.add(ch);
            } else if (ch == ')') {
                Character top = stack.peek();
                //遍历中匹配了
                if (top != null && top.equals('(')) {
                    stack.pop();
                } else {
                    return false;
                }
            } else if (ch == ']') {
                Character top = stack.peek();
                //遍历中匹配了
                if (top != null && top.equals('[')) {
                    stack.pop();
                } else {
                    return false;
                }
            } else if (ch == '}') {
                Character top = stack.peek();
                //遍历中匹配了
                if (top != null && top.equals('{')) {
                    stack.pop();
                } else {
                    return false;
                }
            } else {
                throw new IllegalArgumentException("param valid");
            }
        }
        //全部成对匹配的情况，是：入栈和出栈了，剩余元素为0
        return stack.size()==0;

    }
}
